#include <dbg.h>

#include <cassert>

using namespace std;

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr) {
            return true;
        } else if ((p == nullptr || q == nullptr) || (p->val != q->val)) {
            return false;
        } else {
            return isSameTree(p->left, q->left) &&
                   isSameTree(p->right, q->right);
        }
    }
};

int main() {
    Solution solution;

    // Test Case 1: Same trees
    TreeNode* tree1 = new TreeNode(1, new TreeNode(2), new TreeNode(3));
    TreeNode* tree2 = new TreeNode(1, new TreeNode(2), new TreeNode(3));
    assert(solution.isSameTree(tree1, tree2));

    // Test Case 2: Different values in nodes
    TreeNode* tree3 = new TreeNode(1, new TreeNode(2), new TreeNode(3));
    TreeNode* tree4 = new TreeNode(1, new TreeNode(2), new TreeNode(4));
    assert(!solution.isSameTree(tree3, tree4));

    // Test Case 3: Different structures
    TreeNode* tree5 = new TreeNode(1, new TreeNode(2), new TreeNode(3));
    TreeNode* tree6 = new TreeNode(1, new TreeNode(2), nullptr);
    assert(!solution.isSameTree(tree5, tree6));

    // Test Case 4: Both trees are empty
    TreeNode* emptyTree1 = nullptr;
    TreeNode* emptyTree2 = nullptr;
    assert(solution.isSameTree(emptyTree1, emptyTree2));

    // Test Case 5: One tree is empty, the other is not
    TreeNode* emptyTree3 = nullptr;
    TreeNode* nonEmptyTree = new TreeNode(1);
    assert(!solution.isSameTree(emptyTree3, nonEmptyTree));

    dbg("All test cases passed!");

    return 0;
}